Microfiche appendices 1-33 (of 52 sheets and 3,020 frames) that are attached hereto contain source code in language for programming a computer, are a part of the present disclosure, and are incorporated by reference herein in their entirety.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the patent and trademark office patent files or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates generally to a method implemented by a programmed computer for verifying the functionality of digital circuits during development and testing. More specifically, the invention relates to an automated method for finding defects in a description of a digital circuit that is to be simulated, emulated or implemented in a semiconductor die.
Modern digital electronic circuits are typically designed at the register-transfer (RTL) level in hardware description languages such as Verilog (see xe2x80x9cThe Verilog Hardware Description Language,xe2x80x9d Third Edition, Don E. Thomas and Philip R. Moorby, Kluwer Academic Publishers, 1996) or VHDL (see xe2x80x9cA Guide to VHDLxe2x80x9d, Stanley Mazor and Patricia Langstraat, Kluwer Academic Publishers, 1992). A circuit description in such a hardware description language can be used to generate logic circuit elements as described, for example, in U.S. Pat. No. 5,661,661 granted to Gregory and Segal.
Such hardware description languages facilitate extensive simulation and emulation of the described circuit using commercially available products such as Verilog-XL available from Cadence Design Systems, San Jose, Calif., QuickHDL available from Mentor Graphics, Wilsonville, Oreg., Gemini CSX available from IKOS Systems, Cupertino, Calif., and System Realizer available from Quickturn Design Systems, Mountain View, Calif. These hardware description languages also facilitate automatic synthesis of ASICs (see xe2x80x9cHDL Chip Designxe2x80x9d, by Douglas J. Smith, Doone Publications, 1996; xe2x80x9cLogic Synthesis Using Synopsysxe2x80x9d, Pran Kurup and Taher Abbasi, Kluwer Academic Publishers, 1997) using commercially available products such as Design Analyzer and Design Compiler, available from Synopsys, Mountain View, Calif.
As described in xe2x80x9cArchitecture Validation for Processorsxe2x80x9d, by Richard C. Ho, C. Han Yang, Mark A. Horowitz and David L. Dill, Proceedings 22nd Annual International Symposium on Computer Architecture, pp. 404-413, June 1995, xe2x80x9cmodern high-performance microprocessors are extremely complex machines which require substantial validation effort to ensure functional correctness prior to tapeoutxe2x80x9d (see page 404). As further described in xe2x80x9cValidation Coverage Analysis for Complex Digital Designsxe2x80x9d by Richard C. Ho and Mark A. Horowitz, Proceedings 1996 IEEE/ACM International Conference on Computer-Aided Design, pp. 146-151, November 1996, xe2x80x9cthe functional validation of state-of-the-art digital design is usually performed by simulation of a register-transfer-level modelxe2x80x9d (see page 146).
It is well known to monitor the operation of a simulation test by using, for example, xe2x80x9csnoopersxe2x80x9d generated manually as described at page 463, column 2, in xe2x80x9cHardware/Software Co-Design of the Stanford FLASH Multiprocessorxe2x80x9d, by Mark Heinrich, David Ofelt, Mark A. Horowitz, and John Hennessy, Proceedings of the IEEE, Vol 85, No. 3, pp. 455-466, March 1997, and in xe2x80x9cFunctional Verification Methodology for the PowerPC 604 Microprocessorxe2x80x9d, by James Monaco, David Holloway and Rajesh Raina, Proceedings 33 IEEE Design Automation Conference, pp. 319-324, June 1996.
Another prior art system monitors the operation of a simulation test by using a xe2x80x9cgolden modelxe2x80x9d that is xe2x80x9cwritten without reference to the RTLxe2x80x9d and is xe2x80x9cco-simulated using the same set of test vectorsxe2x80x9d, as described by Chian-Min Richard Ho, in xe2x80x9cValidation Tools for Complex Digital Designsxe2x80x9d, Ph.D. Dissertation, Stanford University Computer Science Department, November 1996 (at page 6, Section 2.1).
Prior-art products (for example, see the xe2x80x9cPurifyxe2x80x9d product from Pure Atria, Sunnyvale, Calif., and the xe2x80x9cInsure++xe2x80x9d product from ParaSoft, Monrovia, Calif.) exist for testing software programs that may be written, for example in the programming language xe2x80x9cCxe2x80x9d described by Brian W. Kernighan and Dennis M. Ritchie in the book xe2x80x9cThe C Programming Languagexe2x80x9d, Second Edition, PTR Prentice Hall, 1988. See xe2x80x9cPurify User""s Guide, Version 4.0xe2x80x9d, Pure Atria Corporation, 1996, and xe2x80x9cInsure++ Automatic Runtime Debugger User""s Guidexe2x80x9d, ParaSoft Corporation, 1996.
A computer, when programmed in accordance with the invention, receives as input a description of a circuit undergoing functional verification (also called xe2x80x9ccircuit-under-verificationxe2x80x9d). The programmed computer uses the circuit""s description to automatically describe additional circuits (hereinafter xe2x80x9ccheckersxe2x80x9d) that can flag defects during verification of the description of the circuit.
In one embodiment, the programmed computer automatically converts a circuit""s description into a graph of (1) nodes that represent, e.g. storage elements (such as registers) or logic elements, or both (sometimes referred to as xe2x80x9ccircuit elementsxe2x80x9d) and (2) connections that represent, e.g. the flow of data among the circuit elements. Next, the programmed computer automatically examines the graph for instances of a pattern (e.g. an arrangement of nodes and connections) that is associated with a known defective behavior. On finding such an instance, the programmed computer generates instructions describing a checker to monitor behavior the instance. The instructions can be, for example, in a hardware description language such as Verilog or VHDL.
When the instructions are implemented, the checker generates an error message each time the monitored behavior conforms to a known defective behavior. Specifically, each checker is coupled to the circuit elements represented by the corresponding instance, and monitors the signals flowing to and/or from the circuit elements for conformance with the known defective behavior.
The checkers can be described in a hardware description language (e.g. the language xe2x80x9cVerilogxe2x80x9d) for use in simulation (or emulation) simultaneous with the simulation (or emulation) of the circuit-under-verification. Alternatively, the checkers can be implemented in a semiconductor die along with the circuit-under-verification. In another embodiment, a programmed computer generates instructions for checkers in a software language (e.g. the C language or machine language depending on the implementation), and during simulation of the circuit-under-verification, such instructions for the checkers are executed directly (e.g. after compilation) by a computer.
The above-described pattern and the known defective behavior are predetermined, e.g. by manual inspection of a number of actual defects and identification of the behavior associated with such defects. Specifically, a number of errors that are identified as functional defects in errata sheets of actual designs are analyzed to identify a common defective behavior, e.g. loss of data in a storage element when the data is overwritten without being used. The errata sheets can include descriptions of conditions related to the defective behavior, for example, buffer overflows, pipeline stalls or unexpected interactions between multiple controllers. Next, the common defective behavior is analyzed to identify an arrangement (of nodes and connections) associated with the common defective behavior.
Thereafter, the computer is programmed to automatically generate a checker that monitors each instance of such an arrangement for behavior in conformance with the common defective behavior. In one example, an arrangement (also called xe2x80x9cregister leak arrangementxe2x80x9d) has at least two nodes for storage elements that are connected sequentially. During automatic examination, on finding two such sequentially connected nodes in the graph, the programmed computer automatically generates a checker for monitoring signals to and from the two nodes.
The checker for a register leak arrangement generates an error message if a first data in a first storage element (represented by a first node), is different from a second data in a second storage element (represented by a second node), and the second data is overwritten by the first data before the second data is used (e.g. written into a third storage element). Therefore, the checker flags the overwriting of unused data in the second storage element by different data. In addition to a checker for the second storage element, the programmed computer automatically generates checkers for other storage elements (e.g. the first and third storage elements) if the other storage elements are also found to be instances of the register leak arrangement.
Automatic generation of one or more checkers to flag known defective behaviors as described herein has several advantages. Specifically, the checkers flag an error as soon as the error occurs in simulation, emulation, or in a semiconductor die, because each checker monitors defective behavior of one instance of an arrangement in the circuit. Therefore, diagnosing errors flagged by automatically generated checkers is much easier than diagnosing errors flagged by end-to-end tests. Furthermore, functional verification can be terminated as soon as an error message is generated, thereby eliminating the generation and diagnosis of additional error messages (generated by continuing the functional verification). Hence, use of checkers as described herein eliminates the prior art need to simulate after an error occurs (e.g. in some cases for several hours) until an effect of the error is detected by an end-to-end test.
Furthermore, automatic generation of checkers as described herein eliminates the labor and problems (for example, missing one or more instances of a predetermined arrangement) involved in manual creation of verification tests. In contrast, the programmed computer automatically traverses the entire graph derived from a circuit""s description and identifies each instance of each predetermined arrangement. Depending on the implementation, the computer can be programmed to generate checkers for (a) all instances, (b) all except user designated instances, or (c) a majority (greater than 50%) of the instances. Therefore, automatically generated checkers as described herein flag errors that may not be found by manual creation of tests.
Furthermore, automatic examination of a graph as described herein allows the detection of instances of an arrangement of nodes and connections that otherwise cannot be found. First, if the nodes of an instance are distributed across multiple modules, the instance is unlikely to be detected on reviewing only the circuit""s description. In contrast, during one implementation of automatic conversion, each call to a module in a hierarchy of modules is automatically instantiated as often as necessary until the graph is completely flattened. Thereafter, when the flattened a graph is automatically examined, instances of an arrangement that span module boundaries are automatically found, resulting in checkers that find unusual defects that may not be found by manually generated tests.
Furthermore, use of a graph as described herein allows an initially determined condition for loading a value into a storage element to be refined. Specifically, the programmed computer adds (e.g. by logically ANDing) a feedback condition (i.e. a condition imposed by the circuit""s description to retain the current value) that is not always logic value TRUE to an initially determined load condition (i.e. a condition to load a storage element). Use of such a refined load condition results in automatic recognition of instances of an arrangement of nodes and connections that are otherwise not found (i.e. without the refinement).
Furthermore, the above-described automatic steps allow the creation of checkers (also called xe2x80x9crelated checkersxe2x80x9d) that use signals generated by other checkers. As an example, a checker for the above-described third storage element detects an error when data is overwritten in the third storage element before being used. The checker for the third storage element uses a signal from the checker for the second storage element to determine that data previously held in the second storage element is currently held in the third storage element.
In one implementation, use of automatically generated checkers as described herein requires no changes to a the description of the circuit-under-verification and no changes to test vectors for testing the circuit. The checkers can be used to monitor the circuit during any verification, e.g. simulation, emulation or implementation in a semiconductor die.